#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//利用快排
//TODO 我哭了 因为什么啊         while (low<high&&nums[high]>=p)  nums[high]>=p 我写成了 higt>=p
int findKthLargest_topk(vector<int>& nums, int k,int low,int high) {

    int p=nums[low];
    while (low<high){

        while (low<high&&nums[high]>=p)
            high--;

        nums[low]=nums[high];

        while (low<high&&nums[low]<p)
            low++;

        nums[high]=nums[low];

    }

    nums[low]=p;

    return low;

}
int  getTopK(vector<int> &nums, int low, int high, int k)
{
    int ktemp=findKthLargest_topk(nums,k,low,high);
    if (ktemp==k)
        return nums[ktemp];
    else if (ktemp>k)
    {
        return getTopK(nums,  low,  ktemp-1,  k);
    } else{
        return getTopK(nums,  ktemp+1,  high,  k);
    }
    return -1;

}

//1 2 3 4 5
int findKthLargest(vector<int>& nums, int k) {

    k=nums.size()-k;
    int begin = 0;
    int end = nums.size() - 1;

    return getTopK(nums,begin,end,k);
}